Algoritmos geneticos

É difícil falar de algoritmos genéticos sem falar antes de Charles Darwin. A ideia de que organismos mais adaptados a determinados meios têm mais chances de sobreviver e repassar suas características a seus descendentes foi criada a partir das observações de uma figura que transformou a Ciência. Trata-se do naturalista Charles Robert Darwin, considerado um gênio cujas descobertas principais foram feitas a bordo de um navio de pesquisa.

O célebre cientista estudou na Universidade de Cambridge e fez grande parte de suas pesquisas enquanto passava pela América do Sul.

Algoritmo de otimização baseado na evolução natural. Observe o exemplo a seguir: imagine uma formiga branca no chão de uma floresta tropical repleta de tamanduás. Elas seriam presas mais fáceis que as formigas de cores mais escuras. Mas como as formigas se tornaram mais escuras? Através do processo evolutivo, onde cruzamentos, mutações ocorrem a fim de tornar a espécie mais adaptada ao ambiente.

Muitos problemas podem ser solucionados com os algoritmos genéticos. O problemas do carteiro chinês é um bom exemplo. Imagine que você precise percorrer um grafo sem passar duas vezes pelo mesmo caminho, ou que precise percorrer esse mesmo grafo com menor custo com combustível.

Charles Darwin foi enviado pelo pai à Universidade de Edimburgo, na Escócia e, apesar de não ter se aprofundado tanto no curso de medicina (ele detestava algumas matérias basilares como anatomia, por exemplo), pôde aprender ainda mais sobre história natural e evolução. Após abandonar a faculdade escocesa, foi, então, mandado para a Universidade de Cambridge, na qual foi aluno do Christ 's College.

Segundo a própria instituição, Darwin era “um estudante jovem, inovador e entusiasmado”. Durante o período de estudos, o neto de Erasmus conheceu o botânico e geólogo britânico John Stevens Henslow, que foi como um mentor para Charles. Foi Henslow quem indicou o então estudante a acompanhar o capitão Robert Fitzroy em uma viagem pela América do Sul a bordo do navio HMS Beagle, que seria um divisor de águas para o cientista.

Darwin embarcou a partir da Inglaterra, em 1831, para a viagem no Beagle com o capitão Fitzroy, que pretendia fazer pesquisas sobre a costa da Patagônia. Durante a expedição, o cientista coletou uma série de fósseis e plantas e observou atentamente os animais e a biologia marinha. Passou pelo Brasil, pela Cordilheira dos Andes e pela Patagônia, mas foi na Ilha de Galápagos que coletou a maior parte de seu material de pesquisa.

A viagem terminou em 1836. Ao reunir seus achados, Darwin notou que os seres que se adaptam melhor ao ambiente tinham mais chances de se reproduzir em relação aos menos adaptados. A descoberta foi chamada de “seleção natural”.

Darwin foi diagnosticado com um problema no coração, que causava crises de angina. Há quem diga que ele sofria da Doença de Chagas, causada pela picada do barbeiro, inseto comum na América Latina. O cientista morreu em Downe, na Inglaterra, em 1882, aos 73 anos e foi enterrado na Abadia de Westminster. O funeral do naturalista foi acompanhado por milhares de pessoas, incluindo membros da comunidade científica da época.

Seleção natural

Vamos então modelar nosso problema com as formigas. Imagine que na nossa floresta tropical hipotética existem dois tipos de formigas e um predador, uma branca e outra preta. As formigas pretas têm mais chance de sobrevivência que as brancas. Dessa forma os mais bem adaptados ao ambiente vão prevalecer.

Dessa forma, para surgirem novos indivíduos precisam haver o crossover, e a mutação. o crossover: é responsável por misturar o genes dos pais. Já a mutação é responsável pelo aparecimento de indivíduos com características diferentes dos genes herdados pelos pais.

Crossover

É a recombinação de características herdadas (pães) dos modelos de origem que ocorrem na geração atual (filhos).

ant_f1 = rgb(0, 0, 0)
ant_m1 = rgb(255, 255, 255)
ant_s1 = ant_f1 + ant_f2
ant_s1 = rgb(128, 128, 128)

O resultado do cruzamento genético da formiga ant_f1 preta com a formiga ant_m1 branca é uma formiga ant_s1 cinza.

Mutação

O aparecimento de características não herdadas, ou seja, alteração na geração atual independente daquelas herdadas. Atributo utilizado para manter a diversidade genéticas das futuras gerações. Principal atributo para evolução das especies no modelo.

ant_s1 = rgb(random.randint(0,255), random.randint(0,255), random.randint(0,255))

Formiga modelo

No exemplo abaixo em python a formiga modelo apresenta os seguintes atributos genéticos cor_rgb(R, G, B), que variam de 0 à 255, ou seja, o genoma da formiga nesse modelo é presentado pela tabela de cores RGB.

ant = rgb(0-255, 0-255, 0-255)

Primeira geração

  1. Crie uma população de indivíduos com genoma aleatório, ou um conjunto de ants com RGB aleatório;

  2. Crie uma função que puna indivíduos com cores mais claras (punisher(genetics));

  3. Crie uma função que recompense os indivíduos de cores mais escuras (benefactor(genetics));

  4. Crie uma função de corte para selecionar os indivíduos mais adaptados (get_genetics());

  5. Crie uma função para utilizar características de dois doares para gerar filhos (crossover());

  6. Crie uma função para causar mutações em um novo indivíduo (mutatis_matutis());

A função benfactor(genetics) é a fitness function, e deve fazer sentido, maximizar as chances de sobrevivência do mais adaptado e diminuir daqueles menos adaptados. Em seguida devemos avaliar todos os indivíduos da população inicial e selecionar aqueles mais adaptados. No nosso exemplo aqueles de ff ou fitness function mais alto. . . .

Considerações

Algoritmo simplificado:

  1. Passo: inicializar a população;

  2. Passo: avaliar cada indivíduo;

  3. Passo: selecionar alguns

  4. Passo: crossover e mutação

  5. Passo: concepção da nova geração

  6. Passo: fim do algoritmo (repita até estar satisfeito com a função objetivo)

About

Author